import itertools
import pandas as pd

# 步骤 1：读取数据
data = [
    ['Milk', 'Bread', 'Butter'],
    ['Milk', 'Bread'],
    ['Milk', 'Butter'],
    ['Bread', 'Butter'],
    ['Milk', 'Bread', 'Butter', 'Cheese'],
    ['Bread', 'Butter', 'Cheese']
]


# 步骤 2：生成候选项集
def create_candidates(data, k):
    candidates = []
    for transaction in data:
        for item in itertools.combinations(sorted(transaction), k):
            if item not in candidates:
                candidates.append(item)
    return candidates


# 步骤 3：计算支持度
def compute_support(data, candidates):
    support = {}
    total_transactions = len(data)
    for candidate in candidates:
        count = sum(1 for transaction in data if set(candidate).issubset(transaction))
        support[candidate] = count / total_transactions
    return support


# 步骤 4：生成频繁项集
def apriori(data, min_support):
    k = 1
    frequent_itemsets = []

    # 初始候选项集为单个商品的集合
    candidates = create_candidates(data, k)
    support = compute_support(data, candidates)

    # 过滤出频繁项集
    frequent_itemsets_k = {item: sup for item, sup in support.items() if sup >= min_support}
    frequent_itemsets.append(frequent_itemsets_k)

    # 不断增加项集的大小
    while frequent_itemsets_k:
        k += 1
        candidates = create_candidates(data, k)
        support = compute_support(data, candidates)
        frequent_itemsets_k = {item: sup for item, sup in support.items() if sup >= min_support}

        if frequent_itemsets_k:
            frequent_itemsets.append(frequent_itemsets_k)

    return frequent_itemsets


# 步骤 5：调用Apriori算法
min_support = 0.5
frequent_itemsets = apriori(data, min_support)

# 输出结果
for k, itemsets in enumerate(frequent_itemsets, start=1):
    print(f"频繁{k}-项集:")
    for itemset, support in itemsets.items():
        print(f"  {itemset}: 支持度 = {support:.2f}")
